import java.util.List;

public class MySingleList implements IList{

    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }


    ListNode head ;

    public void creatlist() {
        ListNode p1 = new ListNode(12);
        ListNode p2 = new ListNode(23);
        ListNode p3 = new ListNode(34);
        ListNode p4 = new ListNode(45);
        ListNode p5 = new ListNode(56);

        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;
        head = p1;

    }

    @Override
    public void addFirst(int data) {

        ListNode p = new ListNode(data);
        if(head == null) {
            head = p;
            return;
        }
        p.next = head;
        head = p;
    }

    @Override
    public void addLast(int data) {

        ListNode p = head;
        ListNode t = new ListNode(data);
        if(head == null) {
            head = t;
            return;
        }
        while (p.next != null) {
            p = p.next;
        }
        p.next = t;
    }

    @Override
    public void addIndex(int index, int data) {

        ListNode t = new ListNode(data);

        int len = size();
        if(index < 0 || index > len) {
            return;
        }
        if(index == 0) {
            t.next = head;
            head = t;
            return;
        }
        int count = index;
        ListNode p = head;
        while ((count - 1) != 0) {

            p = p.next;
            count--;
        }
        t.next = p.next;
        p.next = t;

    }

    @Override
    public boolean contains(int key) {
        if(head == null) {
            return false;
        }
        ListNode p = head;
        while(p != null) {
            if(p.val == key) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {

        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode p = head;
        while (p.next != null) {
            if(p.next.val == key) {
                p.next = p.next.next;
                return;
            }
            p = p.next;
        }

        return;

    }

    @Override
    public void removeAllKey(int key) {

        if(head == null) {
            return;
        }
        ListNode p = head;
        ListNode t = head.next;
        while (t != null) {
            if(t.val == key) {
                p.next = t.next;
                t = t.next;
            } else {
                p = p.next;
                t = t.next;

            }
        }
        if(head.val == key) {
            head = head.next;
        }

    }

    @Override
    public int size() {

        ListNode p = head;
        int t = 0;
        while (p != null) {
            t++;
            p = p.next;
        }
        return t;
    }

    @Override
    public void clear() {

        if(head == null) {
            return;
        }
        ListNode p = head;
        while (p != null) {
            ListNode t = p.next;
            p.next = null;
            p = t;
        }
        head = null;
    }

    @Override
    public void display() {

        if(head == null) {
            return;
        }

        ListNode p = head;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
        System.out.println();
    }

    public void reverse() {
        if(head == null) {
            return;
        }
        ListNode t = head.next;
        head.next = null;
        while (t != null) {

            ListNode k = t.next;
            t.next = head;
            head = t;
            t = k;
        }
    }

    public void reverse2(ListNode p) {
        if(p == null) {
            return;
        }
        ListNode t = p.next;
        p.next = null;
        while (t != null) {

            ListNode k = t.next;
            t.next = p;
            p = t;
            t = k;
        }
    }

    public ListNode middlenode() {
        if(head == null) {
            return null;
        }
        ListNode p = head;
        ListNode t = head;
        while (p != null && p.next != null) {
            p = p.next.next;
            t = t.next;
        }
        return t;
    }

    public ListNode kthnode(int k) {
        if(head == null) {
            return null;
        }
        int len = size();
        if(k <= 0 || k > size()) {
            return null;
        }
        int count = k;
        ListNode p = head;
        ListNode t = head;
        while ((count - 1) != 0) {
            p = p.next;
            if(p == null) {
                return null;
            }
            count--;
        }
        while(p.next != null) {
            p = p.next;
            t = t.next;
        }
        return t;
    }

    public ListNode netList(ListNode A, ListNode B) {
        if(A == null && B == null) {
            return null;
        }
        if(A == null) {
            return B;
        }
        if(B == null) {
            return A;
        }
        while (A.next != null) {
            A = A.next;
        }
        A.next = B;
        return A;
    }

    public ListNode chtnode(int x) {
        ListNode p1 = null;
        ListNode p2 = null;
        ListNode t1 = null;
        ListNode t2 = null;

        ListNode p = head;
        while(p != null) {
            if(p.val < x) {
                if(p1 == null) {
                    p2 = p1 = p;
                } else {
                    p2.next = p;
                    p2 =p2.next;
                }
            } else {

                if(t1 == null) {
                    t1 = t2 = p;
                } else {
                    t2.next = p;
                    t2 = t2.next;
                }
            }
            p = p.next;
        }
        if(p1 == null) {
            return t1;
        }
        p2.next = t1;
        if(t1 != null) {
            t2.next = null;
        }
        return p1;
    }

    public void display2(ListNode p) {
        ListNode t = p;
        while (t != null) {
            System.out.print(t.val + " ");
        }
        System.out.println();
    }

    public boolean huinode() {


        ListNode p = head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode t = slow.next;
        while (t != null) {
            ListNode t1 = t.next;
            t.next = slow;
            slow = t;
            t = t1;
        }

        while (p != slow) {
            if(p.val != slow.val) {
                return false;
            }
            if(p.next == slow) {
                return true;
            }
            p = p.next;
            slow = slow.next;
        }
        return true;
    }

    public ListNode togethernode(ListNode a, ListNode b) {
        int a1 = 0;
        int b1 = 0;
        while (a != null) {
            a1++;
            a = a.next;
        }
        while (b != null) {
            b1++;
            b = b.next;
        }
        int p = a1 - b1;
        if(p < 0) {
            p = b1 - a1;
            while (p != 0) {
                b = b.next;
                p  = p - 1;
            }
            while (a != b) {
                a = a.next;
                b = b.next;
            }
        } else {
            while (p != 0) {
                a = a.next;
                p  = p - 1;
            }
            while (a != b) {
                a = a.next;
                b = b.next;
            }
        }
        return a;
    }

    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }


}
